package q2076_friendRequests;

import CommonClass.UF;

public class Solution {
    /*
    并查集的方式解决
    依次处理每一个请求，并比对交友请求是否和restrictions产生connected
     */
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        UF uf = new UF(n);
        boolean[] ans = new boolean[requests.length];
        for (int i = 0; i < requests.length; i++) {
            int x = requests[i][0], y = requests[i][1];
            // 如果两者还没有交友 则开始判断
            if (!uf.isConnected(x, y)) {
                boolean check = true;
                for (int[] restriction : restrictions) {
                    // 遍历每一个restrict
                    int u = restriction[0], v = restriction[1];
                    // 对比是否出现了x和u在同一个簇 y和v在同一个簇 或者 反过来的情况
                    // 如果有 则不能成功 因为x和y的交友成功 会使得 u 和 v 成为同一个簇
                    if ((uf.isConnected(x, u) && uf.isConnected(y, v)) || (uf.isConnected(x, v) && uf.isConnected(y, u))) {
                        check = false;
                        break;
                    }
                }

                if (check) {
                    ans[i] = true;
                    uf.union(x, y);
                }
            } else {
                // 否则直接记录true 这一步很重要
                ans[i] = true;
            }
        }
        return ans;

    }
}
